F: Zátvorky
25 bodov	Časový limit: 500 ms

Tanečníci sa zoradili do dlhého radu, aby si nacvičili úvodné zábery do oficiálneho videa podujatia. Režisér ale nie je spokojný s rozostavením dám a pánov. Aby bol spokojný, na niektoré miesta do davu musí pridať ďalších tanečníkov. Dámy budeme označovať znakom ( a pánov znakom ). Režisér je spokojný vtedy a len vtedy, ak rad zodpovedá dobre uzátvorkovanému výrazu. Dobre uzátvorkovaný výraz môžeme definovať rekurzívne:

• Prázdny reťazec je dobre uzátvorkovaný výraz.
• Ak R je dobre uzátvorkovaný výraz, potom aj (R) je.
• Ak R a S sú dobre uzátvorkované výrazy, potom aj RS je.
• Ak sa reťazec nedá skonštruovať použitím konečného počtu týchto troch pravidiel, potom nie je dobre uzátvorkovaný výraz.

Na vstupe máte aktuálny rad tanečníkov zapísaných ako reťazec znakov ) a (. Môžete predpokladať, že tento reťazec neobsahuje iné znaky ako tieto dva, že je neprázdny a že nie je dlhší ako 500,000 znakov. Na výstup vypíšte koľko najmenej tanečníkov treba pridať, aby výsledný rad zodpovedal dobre uzátvorkovanému výrazu. Môžete predpokladať, že toto číslo je medzi 0 a 2³⁰ vrátane. > Príklady:

vstup

()())((

výstup

3

vstup

))()

výstup

2

vstup

()()

výstup

0

---